/**
 * Graph.java created by zhangzhidong 
 * at 下午6:34:00 2015年8月8日
 */
package Graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 邻接矩阵表示的图
 * @author Alex
 *
 */
public class Graph {
	
	private final int MAX_VERTS = 20;
	private Vertex vertexList[];
	private int adjMat[][];
	private int nVerts ;
	public Graph(){
		vertexList = new Vertex[MAX_VERTS];
		adjMat = new int [MAX_VERTS	][MAX_VERTS];
		nVerts = 0;
		for(int i =0;i<MAX_VERTS;i++)
			for(int j =0 ;j<MAX_VERTS;j++){
				adjMat[i][j]= 0 ;
			}		
	}
	private void resetAllUnvisited(){
		for(int i=0;i<nVerts;i++){
			vertexList[i].wasVisited = false;
		}
	}
	public void addEdge(char start,char end){
		int index1 = -1 ,index2 = -1;
		for(int i=0;i<nVerts;i++){
			if(vertexList[i].label == start){
				index1 = i;
			}
			if(vertexList[i].label == end){
				index2 = i;
			}
		}
		addEdge(index1, index2);
	}
	
	public void addVertex(char lab){
		vertexList[nVerts++] =  new Vertex(lab);
	}
	public void addEdge(int start,int end){
		adjMat[start][end]=1;
		adjMat[end][start]=1;
		
	}
	private int getAdjUnvisitedVertex(int v){
		for(int i =0;i<nVerts;i++){
			if(adjMat[v][i]==1 && vertexList[i].wasVisited == false ){
				return i;
			}	
		}
		return -1;
	}
	private Queue<Integer> getAllAdjVertex(int v){
		Queue<Integer> queue = new LinkedList<Integer>();
		for(int i=0;i<nVerts ;i++){
			if(adjMat[v][i]==1 && vertexList[i].wasVisited == false){
				queue.add(i);
			}
		}
	
		return queue;
	}
	public void BFS(){
		Queue<Integer> q  =new LinkedList<Integer>();
		q.add(0);
		while(!q.isEmpty()){
		Integer v  =	q.remove();
		// visit 
		System.out.print(vertexList[v].label+",");
		vertexList[v].wasVisited = true;
		//end
		q.addAll(getAllAdjVertex(v));	
			
			
			
		}
		resetAllUnvisited();
	}
	
	
	/**
	 * dfs遍历图
	 * 下午8:07:40
	 */
	public void DFS(){
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(0);
		while(!stack.isEmpty()){
			Integer v =   stack.peek();
			//对结点进行操作
			if(!vertexList[v].wasVisited){
			   System.out.print(vertexList[v].label+",");
			   vertexList[v].wasVisited = true;
			}
			//结束
			Integer adjv =  getAdjUnvisitedVertex(v);
			if(adjv!=-1){
				stack.push(adjv);
			}else{
				stack.pop();
			}
			
		}
	resetAllUnvisited();
		
		
	}
	
	
	public static void main(String args[]){
		Graph  g=  new Graph();
		for (char c = 'A';c<='I';c++){
			g.addVertex(c);
		}
		g.addEdge('A', 'B');
		g.addEdge('A', 'C');
		g.addEdge('A', 'D');
		g.addEdge('A', 'E');
		g.addEdge('B', 'F');
		g.addEdge('F', 'H');
		
		g.addEdge('D', 'G');
		g.addEdge('G', 'I');
		//
		//g.addEdge('F', 'I');
		g.DFS();
		//g.BFS();
	
	}
	
	
	
	
	
}
